今天的題單:
Evaluate Reverse Polish Notation
Course Schedule
思路: 觀察計算的模式,可以利用 stack 來保持正確的計算順序。依照順序讀取 token,當遇到數字就放入 stack,遇到計算符號就把 stack 內的上面兩個數字拿出來計算,把結果 push 進 stack。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
vector<string>::iterator it = tokens.begin();
while (it != tokens.end()) {
int a, b;
if (*it == "+") {
b = stk.top();
stk.pop();
a = stk.top();
stk.pop();
stk.push(a + b);
} else if (*it == "-") {
b = stk.top();
stk.pop();
a = stk.top();
stk.pop();
stk.push(a - b);
} else if (*it == "*") {
b = stk.top();
stk.pop();
a = stk.top();
stk.pop();
stk.push(a * b);
} else if (*it == "/") {
b = stk.top();
stk.pop();
a = stk.top();
stk.pop();
stk.push(a / b);
} else {
stk.push(stoi(*it));
}
it++;
}
return stk.top();
}
};
思路: 把課程當 node,prerequisites當 edge,可以建一個 graph。如果能成功修完所有課,這個 graph 必須沒有環。如果有環,這個環內的課都沒辦法修,道理與 deadlock 相同。因此,這個問題可以轉換成判斷一個有向圖 (Directed Graph) 內有沒有環的問題。
Attempt 1: DFS
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses); // adjcent list
vector<bool> visited(numCourses, false);
vector<bool> rec_stack(numCourses, false);
for (auto& edge : prerequisites) {
graph[edge[0]].push_back(edge[1]);
}
bool has_cycle = false;
// check if there is a cycle in the graph
for (int i = 0; i < numCourses; i++) {
if (check_cycle(i, visited, rec_stack, graph)) {
has_cycle = true;
break;
}
}
return !has_cycle;
}
bool check_cycle(int node, vector<bool>& visited, vector<bool>& rec_stack, vector<vector<int>>& graph) {
visited[node] = true;
rec_stack[node] = true;
for (auto& neighbor : graph[node]) {
if (!visited[neighbor] && check_cycle(neighbor, visited, rec_stack, graph)) {
return true;
} else if (rec_stack[neighbor]) {
return true;
}
}
rec_stack[node] = false;
return false;
}
};